/**
 * Copyright (C) 2008+ Spark Zheng
 *
 * @file	include/heap.h
 * @brief 
 *      Heap module, A basic datastruct module.
 *      Simple heap and merged-heap datastructures
 *
 * @see		dlib
 * @module      dlib
 *
 * @history
 *      version 0.1.0, spark init heap module with min heap 
 */

#ifndef _DLIB_HEAP_H
#define _DLIB_HEAP_H

#ifdef __cplusplus
extern "C" {
#endif

#include "global.h"
#include "lock.h"

/**
 * min heap & max heap
 */

/**
 * heap_relval_fn
 * @brief release the val when needed.
 * heap_dumpout_fn
 * @brief dumpout the val when needed.
 */
typedef void (*heap_relval_fn)(void *val);
typedef void (*heap_dumpout_fn)(void *val);
/**
 * heap_compare_fn
 * @brief key-compare function
 * @return value: (one to two) 0 equal, -1 little, 1 great.
 */
typedef int (*heap_compare_fn)(const void *one, const void *two);

typedef struct simple_heap sheap_t;
typedef struct simple_heap min_heap_t;
typedef struct simple_heap max_heap_t;
typedef struct simple_heap_node sheap_node_t;
typedef struct simple_heap_node min_heap_node_t;
typedef struct simple_heap_node max_heap_node_t;

struct simple_heap {
	uint32_t	heap_capacity;	/** the max capacity */
	uint32_t	heap_current;	/** the current number of heap node */
	heap_compare_fn	heap_compare;	/** compare function */
	heap_relval_fn	heap_relval;	/** release value function */
	sheap_node_t	*heap_nodes;	/** heap nodes */

	dlib_lock_t	heap_lock;
};

struct simple_heap_node {
	void		*heap_data;	/** the data linked in heap */
	uint32_t	heap_index;	/** the data index in heap list */
};

#define SIMPLE_HEAP_EXPANDER		256

#define	SIMPLE_HEAP_CAPACITY(heap)	((heap)->heap_capacity)
#define SIMPLE_HEAP_SIZE(heap)		((heap)->heap_current)
#define SIMPLE_HEAP_COMPARE(heap)	((heap)->heap_compare)
#define SIMPLE_HEAP_RELVAL(heap)	((heap)->heap_relval)
#define SIMPLE_HEAP_HEAD(heap)		((heap)->heap_nodes[0])
#define SIMPLE_HEAP_TAIL(heap)		((heap)->heap_nodes[(heap)->heap_current - 1])

#define SIMPLE_HEAP_DATA(node)		((node)->heap_data)
#define SIMPLE_HEAP_INDEX(node)		((node)->heap_index)


/**
 * simple_heap_init
 * @brief create a simple heap
 * @param capacity: init capacity of simple heap 
 * @param compare_cb: compare callback function
 * @param relval_cb: release value callback function
 */
extern sheap_t *simple_heap_init(uint32_t capacity, heap_compare_fn compare_cb,
		heap_relval_fn relval_cb);

/**
 * simple_heap_exit
 * @brief exit a simple heap
 * @param heap
 */
extern void simple_heap_exit(sheap_t *heap);

/**
 * simple_heap_push
 * @brief push a value into heap
 * @return < 0 error
 * @param heap
 * @param data: input data
 */
extern int simple_heap_push(sheap_t *heap, void *data);

/**
 * simple_heap_pop
 * @brief fetch the min/max element from heap
 * @return < 0 error
 * @param heap:
 * @param data_ptr[out]: the result data ptr
 */
extern int simple_heap_pop(sheap_t *heap, void **data_ptr);

/**
 * simple_heap_delete
 * @brief delete a node in heap
 * @return < 0 error
 * @param heap
 * @param heap_node: the deleted heap_node
 */
extern int simple_heap_delete(sheap_t *heap, sheap_node_t *heap_node);

/**
 * simple_heap_dump
 * @brief dump out statistics
 * @param heap
 * @param dump_cb: dump out callback function
 */
extern void simple_heap_dump(sheap_t *heap, heap_dumpout_fn dump_cb);

/**
 * simple_heap_extract
 * @param heap
 */
extern int simple_heap_extract(sheap_t *heap);

/**
 * simple_heap_change
 * @param heap
 * @param old_data: old data to be changed
 * @param new_data: new data
 */
extern int simple_heap_change(sheap_t *heap, void *old_data, void *new_data);

/**
 * simple_heap_sort
 * @brief heap sort
 * @return < 0 error, > 0 return the number of sorted element
 * @param heap
 * @param array[out]: result array
 * @param array_len: the length of result array
 */
extern int simple_heap_sort(sheap_t *heap, void **array, size_t array_len);


#ifdef __cplusplus
}
#endif
#endif
